什么是洗牌算法

问题

小E最近在设计一款斗地主小游戏，为了保证发到玩家手中的牌具有随机性，小E必须对现实世界中的洗牌过程进行模拟。看似简单的一个问题，却难住了小E。

于是，小E向老师请教。

思路

点评：上面即为洗牌算法的思想，其本质是对数组元素进行随机重排。数组中每个元素经过洗牌算法后落在数组某个位置上的概率是相等的，洗牌算法在牌类游戏中非常有用。我们最终将算法的时间复杂度优化到了O（n），空间复杂度优化到了O（1）。

代码实现

下面是作者用JavaScript实现的代码，仅供参考！（建议大家自己动手实现一遍）

//对数组中的元素进行随机重新排列，并返回
//arr:数组
function shuffle(arr) {
    for(let i = arr.length - 1; i >= 0; i--) {
        //随机从0-i中选择一个下标
        let randomIndex = Math.floor(Math.random() * (i + 1));
        //将选中的元素与arr[i]交换
        let t = arr[randomIndex];
        arr[randomIndex] = arr[i];
        arr[i] = t;
    }
    //返回随机重排后的数组
    //随机重排过程发生在原数组上，并未产生新数组
    return arr;
}

往期